package com.promote.algorithm;

/**
 * @ClassName SearchMatrix
 * Description 力扣--74 搜索二维矩阵
 * @Author LiZiHao
 * Date 2021/11/10 10:39
 * @Version 1.0
 **/
public class SearchMatrix {

    public static boolean searchMatrix(int[][] matrix, int target) {

        int rowNum = searchFirstColumn(matrix, target);
        if (rowNum < 0 ){
            return false;
        }
        return searchRow(matrix[rowNum],target);
    }

    /**
     * 二分查找第一列数值
     * @param matrix
     * @param target
     * @return
     */
    public static int searchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length-1;
        while (low < high) {
            int mid = (high - low + 1)/2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else{
                high = mid - 1;
            }
        }
        return low;
    }

    /**
     * 根据匹配的行数，匹配目标值
     * @param row
     * @param target
     * @return
     */
    public static boolean searchRow(int[] row, int target) {
        int low = 0;
        int high = row.length-1;
        while (low <= high) {
            int mid = (high - low)/2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid -1;
            } else {
                low = mid +1;
            }
        }
        return false;
    }

    public static void main(String[] args) {

        int[][] matrix = {{1,3}};
        int target = 3;
        boolean b = searchMatrix(matrix, target);
        System.out.println(b);
    }
}
